package com.hop.sort;

/**
 * 选择排序
 * @author Administrator
 *
 */
public class ExchangeSort {
	
	/**
	 * 冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，
	 * 让较大的数往下沉，较小的往上冒。
	 * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
	 *•若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
	 *•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
	 *•起泡排序平均时间复杂度为O(n2)
	 * @param a
	 */
	public void maop(int a[]){
		long start = System.currentTimeMillis();
		for(int i=0;i<a.length;i++){
			for(int j=0; j<a.length-i-1;j++){
				if(a[j]>a[j+1]){
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		long ent = System.currentTimeMillis();
		System.out.print("执行时间："+(start-ent)+"MS");
	}
	/**
	 * 快速排序
	 * 1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
	 * 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
	 * 3）此时基准元素在其排好序后的正确位置
	 * 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序
	 * @param a
	 */
	public void quick(int a[]){
		long start = System.currentTimeMillis();
		if(a.length>0){
			quickSort(a,0,a.length-1);
		}	
		long ent = System.currentTimeMillis();
		System.out.print("执行时间："+(start-ent)+"MS");
	}
	
	public static void quickSort(int a[],int low,int high){
		if(low<high){
			int middle = getMiddle(a,low,high);
			quickSort(a, 0, middle-1);
            quickSort(a, middle+1, high);
		}
	}
	
	public static int getMiddle(int a[],int low,int high){
		int temp = a[low];//基准元素
        while(low<high){
            //找到比基准元素小的元素位置
            while(low<high && a[high]>=temp){
                high--;
            }
            a[low] = a[high]; 
            while(low<high && a[low]<=temp){
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
	
}
